package T115;

public class Main {
}

class Solution {
    public int numDistinct(String s, String t) {
        char[] arrS = s.toCharArray();
        char[] arrT = t.toCharArray();
        int[][] dp = new int[arrS.length+1][arrT.length+1];
        for(int i = 0; i<arrS.length ;i++ ) {
            dp[i][0] = 1;
        }
        for(int i = 1; i<=arrS.length ;i++) {
            for(int j = 1; j<=arrT.length ;j++) {
                dp[i][j] = dp[i-1][j];
                if(arrS[i-1]==arrT[j-1]) {
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
        return dp[arrS.length][arrT.length];
    }
}